package traverser;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ListSorter {
	String[] data;
	String[] newData;
	private int number;

	// constructor
	public ListSorter(String[] data) {
		this.data = data;
	}

	// sorts the list/array
	public String[] sort() {
		this.newData = removeDuplicates();

		data = null;
		number = newData.length;

		mergesort(0, number - 1);

		return newData;
	}

	public String[] removeDuplicates() {
		List<String> list = Arrays.asList(data);
		Set<String> set = new HashSet<String>(list);

		String[] result = new String[set.size()];
		set.toArray(result);
		return result;
	}

	private void mergesort(int low, int high) {
		// Check if low is smaller then high, if not then the array is
		// sorted
		if (low < high) {
			// Get the index of the element which is in the middle
			int middle = (low + high) / 2;
			// Sort the left side of the array
			mergesort(low, middle);
			// Sort the right side of the array
			mergesort(middle + 1, high);
			// Combine them both
			merge(low, middle, high);
		}
	}

	private void merge(int low, int middle, int high) {

		// Helperarray
		String[] helper = new String[number];

		// Copy both parts into the helper array
		for (int i = low; i <= high; i++) {
			helper[i] = newData[i];
		}

		int i = low;
		int j = middle + 1;
		int k = low;
		// Copy the smallest values from either the left or the right side
		// back
		// to the original array
		while (i <= middle && j <= high) {
			if (helper[i].compareTo(helper[j]) < 0) {
				newData[k] = helper[i];
				i++;
			} else {
				newData[k] = helper[j];
				j++;
			}
			k++;
		}
		// Copy the rest of the left side of the array into the target array
		while (i <= middle) {
			newData[k] = helper[i];
			k++;
			i++;
		}
		helper = null;

	}
}
